package functions.images;

import java.nio.ByteBuffer;
import java.util.ArrayList;
import java.util.Date;
import java.util.Random;

import com.google.appengine.api.blobstore.BlobKey;
import com.google.appengine.api.blobstore.BlobstoreService;
import com.google.appengine.api.blobstore.BlobstoreServiceFactory;
import com.google.appengine.api.files.AppEngineFile;
import com.google.appengine.api.files.FileService;
import com.google.appengine.api.files.FileServiceFactory;
import com.google.appengine.api.files.FileWriteChannel;
import com.google.appengine.api.images.Image;
import com.google.appengine.api.images.ImagesService;
import com.google.appengine.api.images.ImagesServiceFactory;

public class AlgorithmsForCloudProject {
    private static BlobstoreService blobstoreService = BlobstoreServiceFactory.getBlobstoreService();

	public static void main(String[] args){
		//int n = 400;
		//int shuffles = 10000000;

		// Array of different dimensions to test
		int nArr[] = {5, 10, 15, 40, 100, 500, 1000, 2000, 3000, 4000, 5000};

		// Result array
		ArrayList<double[]> arr = new ArrayList<double[]>();
		
		// Loop for the testing of different dimensions
		for(int i = 0; i < nArr.length; ++i){
			int n = nArr[i];
			System.out.println("n = " + n);
			
			// Loop for the testing of different shuffles per dimension
			for(int shuffles = 10; shuffles <= 100000000; shuffles*= 10){
				double[] temp = new double[5];
				temp[0] = n;
				temp[1] = shuffles;
				
				// Get the current time, generate the puzzle using the third version, and report the total time to shuffle
				long time = new Date().getTime();
				generateShuffledPuzzle_v3(n, shuffles);
				temp[2] = (new Date().getTime() - time)/1000.0;
				
				// On my current machine, this version will run out of heapspace at dimension = 4288 x 4288
				if(n <= 4287){
					// Get the current time, generate the puzzle using the third version, and report the total time to shuffle
					time = new Date().getTime();
					/*prettyPrintBoard(*/generateShuffledPuzzle_v2(n, shuffles);//, n);
					temp[3] = (new Date().getTime() - time)/1000.0;
				} else {
					temp[3] = 100;
				}
				
				// On my current machine, this version will run out of heapspace around dimension = 1000 x 1000
				if(n <= 1000){
					// Get the current time, generate the puzzle using the third version, and report the total time to shuffle
					time = new Date().getTime();
					generateShuffledPuzzle(n, shuffles);
					temp[4] = (new Date().getTime() - time)/1000.0;
				} else {
					temp[4] = 100;
				}
				arr.add(temp);
			}
		}
		
		// Print out the results
		for(int j = 0; j < arr.size(); ++j){
			double[] temp = arr.get(j);
			
			// Add a * if version two is better than version 3
			if(temp[2] < temp[3]){
				System.out.print("*");
			}
			
			// Add a ^ if version two is better than version 1
			if(temp[4] < temp[3]){
				System.out.print("^");
			}
			System.out.println("n: " + temp[0] + "   \tshuffles: " + temp[1] + "   \tv3: " + temp[2] + "  \tv2: " + temp[3] + "  \tv3: " + temp[4]);
		}
	}
	
	/*
	 * This function will take in an image and a dimension and will split it into dimension*dimension other images and
	 * return an arraylist of blob-keys referring to those smaller images
	 */
	public static ArrayList<BlobKey> splitIntoArray(Image img, int n){
		ImagesService imgService = ImagesServiceFactory.getImagesService();
		ArrayList<BlobKey> imgArr = new ArrayList<BlobKey>();
		
		blobstoreService.createUploadUrl("/upload");

		// Loop through and crop the images into smaller images.  Add the blob-keys that result to the return array
		for (double i = 0; i < n; ++i) {
			for (double j = 0; j < n; ++j) {
				//Make a temp copy of the image, just in case anything changes
				Image temp = ImagesServiceFactory.makeImage(img.getImageData());
				
				// Perform cropping
				temp = imgService.applyTransform(ImagesServiceFactory.makeCrop(j/n, i/n, (j + 1)/n, (i + 1)/n), temp);
				try {
					// Pass it to the next function that will programmatically upload it to the blobstore
					imgArr.add(please(temp));
				} catch (Exception e) {
					e.printStackTrace();
				}
			}
		}
		
		return imgArr;
	}
	
	/*
	 * This function will take an image and programmatically upload it to the blobstore.  It will return the blob-key of the uploaded image
	 */
	public static BlobKey please(Image img) throws Exception{
		FileService fileService = FileServiceFactory.getFileService();
		AppEngineFile file = fileService.createNewBlobFile("image/"+img.getFormat().toString().toLowerCase());
		
		boolean lock = true;
		FileWriteChannel writeChannel = fileService.openWriteChannel(file, lock);
		writeChannel.write(ByteBuffer.wrap(img.getImageData()));
		writeChannel.closeFinally();
		
		return fileService.getBlobKey(file);
	}
	
	/*
	 * pretty print a two dimensional arraylist
	 */
	public static void prettyPrintArrIntArr(ArrayList<int[]> arr){
		for(int i = 0; i < arr.size(); ++i){
			int[] elem = arr.get(i);
			System.out.print("(");
			for(int j = 0; j < elem.length; ++j){
				System.out.print(elem[j] + " ");
			}
			System.out.println(")");
		}
	}
	
	/*
	 * pretty print a board
	 */
	public static void prettyPrintBoard(int[] arr, int n){
		for(int i = 0; i < n; i++){
			for(int j = 0; j < n; j++){
				if (arr[(i * n) + j] == (n * n) - 1) {
					System.out.print("* ");
					for(int k = 1; k < Math.log10((n*n)-1); ++k){
						System.out.print(" ");
					}
				} else {
					int num = arr[(i*n) + j];
					int k;
					System.out.print(num + " ");
					if(num == 0){
						k = 1;
					} else {
						k = (int) (Math.log10(arr[(i*n)+j]) + 1);
					}
					for(; k < Math.log10((n*n)-1); ++k){
						System.out.print(" ");
					}
				}
			}
			System.out.println();
		}
	}
	
	/*
	 * pretty print a single arraylist
	 */
	@SuppressWarnings("rawtypes")
	public static void prettyPrintArrList(ArrayList arr){
		for(int i = 0; i < arr.size(); ++i){
			System.out.print(arr.get(i) + " ");
		}
	}
	
	/*
	 * A helper function for the second version of my shuffling algorithm.  This function will return an n*n sized array that
	 * when shown as a square will classify each space according to:
	 * 	TOP_LEFT, TOP, TOP_RIGHT, LEFT, MIDDLE, RIGHT, BOTTOM_LEFT, BOTTOM, BOTTOM_RIGHT
	 *     0       1       2        3      4      5         6          7         8
	 */
	public static int[] generateShuffleArray_v2(int n){
		// TOP_LEFT, TOP, TOP_RIGHT, LEFT, MIDDLE, RIGHT, BOTTOM_LEFT, BOTTOM, BOTTOM_RIGHT
		//    0       1       2        3      4      5         6          7         8
		int[] arr = new int[n*n];
		int i = 0;
		long time = new Date().getTime();
		
		// Start populating the array, the top left piece is always 0
		arr[i++] = 0;
		
		// The rest of the top row (1 - (n-2)) are considered the "top"
		for(; i < n-1; ++i){
			arr[i] = 1;
		}
		
		// The last piece on the top row is always 2
		arr[i++] = 2;
		
		// For every other row, excluding the bottom, mark it correctly as 3,4,...,4,5
		for(int j = 1; j < n-1; ++j){
			arr[i++] = 3;
			for(int k = 1; k < n-1; ++k){
				arr[i++] = 4;
			}
			arr[i++] = 5;
		}
		
		// The bottom left piece will be a 6
		arr[i++] = 6;
		
		// The rest of the bottom row, excludign the last piece, will be a 7
		for(;i<(n*n)-1;++i){
			arr[i] = 7;
		}
		
		// The bottom right piece is always an 8
		arr[i++] = 8;
		
		System.out.println((new Date().getTime() - time)/1000.0 + " seconds to finish populating the shuffle array");
		return arr;
	}
	
	/*
	 * Another helper function for the second version of my algorithm.  This will take in the star position (the one that can move) and,
	 * based on the shuffle array, will return an integer array of the next valid moves.
	 */
	public static int[] getNextArr(int starPos, int pos, int n){
		// TOP_LEFT, TOP, TOP_RIGHT, LEFT, MIDDLE, RIGHT, BOTTOM_LEFT, BOTTOM, BOTTOM_RIGHT
		//    0       1       2        3      4      5         6          7         8
		int[] toReturn = new int[1];
		switch(pos){
			case 0:
				int[] temp0 = {1,n};
				toReturn = temp0;
				break;
			case 2:
				int[] temp2 = {n-2,(2*n)-1};
				toReturn = temp2;
				break;
			case 6:
				int[] temp6 = {(n*n)-n+1,n*(n-2)};
				toReturn = temp6;
				break;
			case 8:
				int[] temp8 = {(n*n)-n-1, (n*n)-2};
				toReturn = temp8;
				break;
			case 1:
				int[] temp1 = {starPos-1, starPos+1, starPos+n};
				toReturn = temp1;
				break;
			case 3:
				int[] temp3 = {starPos-n, starPos+1, starPos+n};
				toReturn = temp3;
				break;
			case 5:
				int[] temp5 = {starPos-n, starPos-1, starPos+n};
				toReturn = temp5;
				break;
			case 7:
				int[] temp7 = {starPos-n, starPos-1, starPos+1};
				toReturn = temp7;
				break;
			case 4:
				int[] temp4 = {starPos-n, starPos-1, starPos+1, starPos+n};
				toReturn = temp4;
				break;
			default:
				System.err.println("Houston, we have a problem!");
		}
		return toReturn;
	}
	
	/*
	 * A helper function for the first version of my shuffling algorithm.  This function will take in the dimension of the puzzle
	 * and will return a n*n sized array of Integer arraylists.  The index into this array corresponds to the location of the star
	 * (the movable piece) and will be an arrayList of integers to where that star can validly move.
	 */
	public static ArrayList<Integer>[] generateShuffleArray(int n){
		
		@SuppressWarnings("unchecked")
		ArrayList<Integer>[] arr = new ArrayList[n*n];
		for(int i = 0; i < n*n; ++i){
			arr[i] = new ArrayList<Integer>();
		}
		
		long time = new Date().getTime();
		for(int i = 0; i < (n*n)-1; ++i){
			
			// Always look at the current piece and pieces after that, so as to not double count.
			
			// If the two pieces are next to each other and on the same row, add them to each other's arrayLists
			if(i/n == (i+1)/n){
				arr[i].add(i+1);
				arr[i+1].add(i);
			}
			
			// If the two pieces are in the same column, add them to each other's arrayLists
			if(i+n < (n*n)){
				arr[i].add(i+n);
				arr[i+n].add(i);
			}
		}
		System.out.println((new Date().getTime() - time)/1000.0 + " seconds to finish populating the shuffle array");
		return arr;
	}
	
	public static ArrayList<int[]> trim(ArrayList<int[]> arr, int n, int[] seed){
		int max = (n*n) - 1;
		ArrayList<int[]> toReturn = new ArrayList<int[]>();
		for(int i = 0; i < arr.size(); ++i){
			int[] temp = arr.get(i);
			if(seed[temp[0]] == max || seed[temp[1]] == max){
				toReturn.add(temp);
			}
		}
		return toReturn;
	}
	
	/*
	 * This is the third version of my shuffling algorithm.  In this edition, I tried to take out the extra array and
	 * function calls from the second version.  However, since multiple calculations needed to take place in order to get
	 * to the most likely state (the star position and the tile it can switch with are in the middle), this version was
	 * slower than the second version.
	 */
	public static int[] generateShuffledPuzzle_v3(int n, int shuffles){
		int[] seed = new int[n*n];
		
		// Populate the initial array
		for(int i = 0; i < n*n; ++i){
			seed[i] = i;
		}
		
		Random gen = new Random();
		long time = new Date().getTime();
		int starPos = (n*n)-1;
		
		// For each shuffle, make one valid move
		for(int i = 0; i < shuffles; ++i){
			
			// Generate a random number that is divisible my all of the possible valid moves from the star position
			int rand = gen.nextInt(12);
			int newPos = -1;
			if(starPos >= n*(n-1)){
				//bottom left, bottom, bottom right
				if(starPos == n*(n-1)){
					//bottom left
					rand %= 2;
					if (rand == 0){
						newPos = starPos-n;
					} else {
						newPos = starPos+1;
					}
				} else if (starPos == (n*n)-1){
					//bottom right
					rand %= 2;
					if(rand == 0){
						newPos = starPos-n;
					} else {
						newPos = starPos-1;
					}
				} else {
					//bottom
					rand %= 3;
					if(rand == 0){
						newPos = starPos-n;
					} else if (rand == 1){
						newPos = starPos-1;
					} else {
						newPos = starPos+1;
					}
				}
			} else if (starPos < n){
				//top left, top, top right
				if(starPos == 0){
					//top left
					rand %= 2;
					if(rand == 0){
						newPos = starPos+1;
					} else {
						newPos = starPos+n;
					}
				} else if (starPos == (n-1)){
					//top right
					rand %= 2;
					if(rand == 0){
						newPos = starPos-1;
					} else {
						newPos = starPos+n;
					}
				} else {
					//top
					rand %= 3;
					if(rand == 0){
						newPos = starPos-1;
					} else if (rand == 1) {
						newPos = starPos+1;
					} else {
						newPos = starPos+n;
					}
				}
			} else if (starPos % n == 0){
				//left
				rand %= 3;
				if(rand == 0){
					newPos = starPos-n;
				} else if (rand == 1) {
					newPos = starPos+1;
				} else {
					newPos = starPos+n;
				}
			} else if (starPos % n == (n-1)){
				//right
				rand %= 3;
				if(rand == 0){
					newPos = starPos-n;
				} else if (rand == 1) {
					newPos = starPos-1;
				} else {
					newPos = starPos+n;
				}
			} else {
				// middle
				rand %= 4;
				if(rand == 0){
					newPos = starPos-n;
				} else if (rand == 1) {
					newPos = starPos-1;
				} else if (rand == 2) {
					newPos = starPos+1;
				} else {
					newPos = starPos+n;
				}
			}
			if (newPos < 0) {
				--i;
				System.out.println("PROBLEM");
				continue;
			}
			
			// Switch the two tiles
			seed[starPos] = seed[newPos];
			seed[newPos] = (n*n)-1;
			
			// Keep track of the new star position
			starPos = newPos;
		}
		System.out.println((new Date().getTime() - time)/1000.0 + " seconds for the shuffling");
		return seed;
	}
	
	/*
	 * This is the second version of my shuffle algorithm.  This one sought to take care of the massive waste of
	 * space complexity in the first version.  The strategy was to create a shadow array which would let me keep
	 * track of what "class" the current tile fell in to, and know what to switch it on from there.
	 */
	public static int[] generateShuffledPuzzle_v2(int n, int shuffles){
		int[] seed = new int[n*n];
		
		// Populate the initial array
		for(int i = 0; i < n*n; ++i){
			seed[i] = i;
		}
		
		// Generate the shadow array
		int[] shuffleArr = generateShuffleArray_v2(n);
		
		Random gen = new Random();
		long time = new Date().getTime();
		int starPos = (n*n)-1;
		
		// For each shuffle, make one valid move
		for(int i = 0; i < shuffles; ++i){
			
			// Obtain the array of possible moves by calling a helper function
			int[] tempArr = getNextArr(starPos, shuffleArr[starPos], n);
			
			// Randomly choose which valid move to fire
			int temp = tempArr[gen.nextInt(tempArr.length)];
			
			// Error "handling"
			if (seed[starPos] != (n * n) - 1) {
				--i;
				System.out.println("PROBLEM");
				continue;
			}
			
			// Swap the tiles and keep track of the star position
			seed[starPos] = seed[temp];
			seed[temp] = (n*n)-1;
			starPos = temp;
		}
		System.out.println((new Date().getTime() - time)/1000.0 + " seconds for the shuffling");
		return seed;
	}
	
	/*
	 * This is the first version of my shuffling algorithm.  I was not so much concerned about space
	 * complexity as I was concerned about improving over the naive "pick a location and see if it can
	 * be swapped with the star position, if it cant, repick" algorithm.  This succeeded, but runs out
	 * of heap space very quickly due to the poor space considerations
	 */
	public static int[] generateShuffledPuzzle(int n, int shuffles){
		int[] seed = new int[n*n];
		
		// Populate the initial array
		for(int i = 0; i < n*n; ++i){
			seed[i] = i;
		}
		
		// Obtain the list of valid shuffles by use of a helper function
		ArrayList<Integer>[] shuffleArr = generateShuffleArray(n);

		Random gen = new Random();
		long time = new Date().getTime();
		int starPos = (n*n)-1;
		
		// For each shuffle, make one valid move
		for(int i = 0; i < shuffles; ++i){
			
			// From the valid shuffles list, get the one that we want to use
			ArrayList<Integer> tempAL = shuffleArr[starPos];
			
			// Pick a random, valid move from that list
			int temp = tempAL.get(gen.nextInt(tempAL.size()));
			
			// Error "handling"
			if (seed[starPos] != (n * n) - 1) {
				--i;
				System.out.println("PROBLEM");
				continue;
			}
			
			// Swap the tiles and keep track of the star position
			seed[starPos] = seed[temp];
			seed[temp] = (n*n)-1;
			starPos = temp;
		}
		System.out.println((new Date().getTime() - time)/1000.0 + " seconds for the shuffling");
		return seed;
	}
}
